|
An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields such as number theory, and more recently in cryptography and Digital Signature Authentication (See elliptic curve cryptography and elliptic curve DSA). While in number theory they have important consequences in the solving of Diophantine equations, with respect to cryptography, they enable us to make effective use of the difficulty of the discrete logarithm problem (DLP) for the group , of elliptic curves over a finite field , where ''q'' = ''p''''k'' and ''p'' is a prime. The DLP, as it has come to be known, is a widely used approach to public key cryptography, and the difficulty in solving this problem determines the level of security of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular ''p'' > 3. For curves over fields of small characteristic more efficient algorithms based on ''p''-adic methods exist. ==Approaches to counting points on elliptic curves== There are several approaches to the problem. Beginning with the naive approach, we trace the developments up to Schoof's definitive work on the subject, while also listing the improvements to Schoof's algorithm made by Elkies (1990) and Atkin (1992). Several algorithms make use of the fact that groups of the form are subject to an important theorem due to Hasse, that bounds the number of points to be considered. The Hasse's theorem states that if ''E'' is an elliptic curve over the finite field , then the cardinality of satisfies : ==Naive approach== The naive approach to counting points, which is the least sophisticated, involves running through all the elements of the field and testing which ones satisfy the Weierstrass form of the elliptic curve : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「counting points on elliptic curves」の詳細全文を読む スポンサード リンク
|